Given a communications network comprising multiple network devices, it is a problem to set up secure connections between pairs of such network devices. One way to achieve this is described in C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung, “Perfectly-Secure Key distribution for Dynamic Conferences”, Springer Lecture Notes in Mathematics, Vol. 740, pp. 471-486, 1993 (referred to as ‘Blundo’).
It assumes a central authority, also referred to as the network authority or as the Trusted Third Party (TTP), that generates a symmetric bivariate polynomial f(x,y), with coefficients in the finite field F with p elements, wherein p is a prime number or a power of a prime number. Each device has an identity number in F and is provided with local key material by the TTP. For a device with identifier the local key material are the coefficients of the polynomial f(η,y).
If a device η wishes to communicate with device η′, it uses its key material to generate the key K(η, η′)=f(η, η′). As f is symmetric, the same key is generated.
In the patent application with title “KEY SHARING DEVICE AND SYSTEM FOR CONFIGURATION THEREOF” by the same applicant as the current patent application an improved method of configuring network devices for key sharing is given. The patent application has application No. 61/740,488 and filing data 2012 Dec. 21 (incorporated herein by reference) and will be referred to as the ‘configuring application’.
In a collection of multiple network devices, each one has its own unique identity number and local key material. The local material has been derived from a secret polynomial; the latter is often a bivariate polynomial. In the configuring application it is explained how the secret polynomial may be chosen to obtain higher resistance against certain attacks. One such attack in particular is a collusion attack in which multiple network devices try to reconstruct the secret polynomial.
The network devices need to do some work to establish the shared key. For example, consider a pair of network devices that each received a univariate polynomial obtained for them from a secret bivariate polynomial. When two network devices need to establish a cryptographic key among them, they obtain the identity number of the other device and combine it with their local key material to obtain the shared key.
One way to derive the shared key is for each one of the network devices to substitute the identity number of the other network device into its univariate polynomial, reducing the result of the substituting modulo a public modulus and then followed by reducing modulo a key modulus. The key modulus is a power of 2, the exponent of the power being at least the key length.
Thus in a first step towards obtaining the shared key a network device may have to perform a polynomial evaluation in a particular point followed by two reductions.